use std::{fmt::Display, ops::{AddAssign, Add}};

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct LinkList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(data: T) -> Node<T> {
        Node { data, next: None }
    }
}

#[allow(dead_code)]
impl<T> LinkList<T> {
    pub fn new() -> LinkList<T> {
        LinkList { head: None }
    }

    pub fn prepend(&mut self, data: T) -> &mut Self {
        let mut node = Box::new(Node::new(data));
        match self.head {
            None => self.head = Some(node),
            Some(_) => {
                node.next = self.head.take();
                self.head = Some(node);
            }
        }
        self
    }

    pub fn append(&mut self, data: T) -> &mut Self{
        let node = Box::new(Node::new(data));
        match &mut self.head {
            None => self.head = Some(node),
            Some(_) => {
                let mut last_node = &mut self.head;
                while let Some(v) = last_node {
                    if v.next.is_none() {
                        v.next = Some(node);
                        break;
                    }
                    last_node = &mut v.next;
                }
            },
        }

        self
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.data
        })
    }

    pub fn len(&self) -> usize {
        let mut len = 0;
        let mut node = &self.head;
        while let Some(v) = node {
            node = &v.next;
            len += 1;
        }
        len
    }

    pub fn reverse(&mut self) {
        let mut prev = None;
        while let Some(mut node) = self.head.take() {
            self.head = node.next;
            node.next = prev;
            prev = Some(node);
        }
        self.head = prev;
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.as_deref() }
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut { next: self.head.as_deref_mut() }
    }
    
}

impl<T: Display> Display for LinkList<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            write!(f, "None\n")?;
        } else {
            let mut next = self.head.as_ref();
            while let Some(node) = next {
                write!(f, "{} -> ", node.data)?;
                next = node.next.as_ref();
            }
            write!(f, "None\n")?;
        }

        Ok(())
    }
}

impl<T> AddAssign for LinkList<T> {
    fn add_assign(&mut self, rhs: Self) {
        let mut last_node = &mut self.head;
        while let Some(v) = last_node {
            if v.next.is_none() {
                v.next = rhs.head;
                break;
            }
            last_node = &mut v.next;
        }
    }
}

impl<T> Add for LinkList<T> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        let mut result_list = LinkList::new();
        result_list.head = self.head;

        let mut last_node = &mut result_list.head;
        while let Some(v) = last_node {
            if v.next.is_none() {
                v.next = rhs.head;
                break;
            }
            last_node = &mut v.next;
        }

        result_list
    }
}

pub struct IntoIter<T>(LinkList<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.data
        })
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.data
        })
    }
}
